// 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

//  

// 示例 1：

// 输入："abc"
// 输出：3
// 解释：三个回文子串: "a", "b", "c"
// 示例 2：

// 输入："aaa"
// 输出：6
// 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
//  

// 提示：

// 输入的字符串长度不会超过 1000 。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/* 暴力求解
时间复杂度：O(n^3)
空间复杂度：O(1)
*/
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int res{n};
        for (int i{0}; i < n; ++i) {
            for (int j{i+1}; j < n; ++j) {
                if (isPalindrome(s, i, j)) {
                    ++res;
                }
            }
        }
        return res;
    }
    bool isPalindrome(const string& s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) return false;
            ++i;
            --j;
        }
        return true;
    }
};

/* 中心拓展 - 两次循环
枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，
当两个指针指向的元素相同的时候就拓展，否则停止拓展。
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int res{n}; // 所有单个字母都是回文串
        // 奇数
        for (int i{1}; i < n; ++i) {
            int l{i - 1};
            int r{i + 1};
            while (l >= 0 && r < n && s[l] == s[r]) {
                ++res;
                --l;
                ++r;
            }
        }
        // 偶数
        for (int i{0}; i < n; ++i) {
            int l{i};
            int r{i + 1};
            while (l >= 0 && r < n && s[l] == s[r]) {
                ++res;
                --l;
                ++r;
            }
        }
        return res;
    }
};

/* 中心拓展 - 一次循环
枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，
当两个指针指向的元素相同的时候就拓展，否则停止拓展。
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int res{0};
        for (int i{0}; i < 2 * n - 1; ++i) {
            int l = i / 2;
            int r = i / 2 + i % 2;
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
                ++res;
            }
        }
        return res;
    }
};

/* Manacher算法
马拉车
Manacher 算法是在线性时间内求解最长回文子串的算法。
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }

        return ans;
    }
};